package heap;

import java.util.Arrays;

public class MaxHeap {

    //    private static final int[] array = {27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0};
    private static final int[] array = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

    public static void main(String[] args) {
/*        maxHeapIfy(2);
        System.out.println(Arrays.toString(array));*/
        buildMaxHeap();
    }

    private static void maxHeapIfy(int i) {
        System.out.println(i);
//        如果i是叶子节点，
        if (i > Math.floorDiv(array.length, 2) + 1) return;
        int leftIndex = 2 * i + 1;
        if (leftIndex >= array.length) return;
        int largest = array[leftIndex] > array[i] ? leftIndex : i;
        int rightIndex = 2 * (i + 1);
        if (rightIndex < array.length){
            largest = array[rightIndex] > array[largest] ? rightIndex : largest;
        }

        if (largest != i) {
            int temp = array[largest];
            array[largest] = array[i];
            array[i] = temp;
            maxHeapIfy(largest);
        }
    }

    private static void buildMaxHeap() {
        for (int i = Math.floorDiv(array.length, 2) + 1; i >= 0; i--) {
            maxHeapIfy(i);
        }
        System.out.println(Arrays.toString(array));
    }
}
